Trong độ phức tạp truyền thông không đơn định, Alice và Bob được sử dụng máy tiên tri. Sau khi nhận được hướng dẫn của máy tiên tri, hai người trao đổi thông tin để tính f(x,y). Độ phức tạp truyền thông không đơn định được định nghĩa là tổng lớn nhất trong mọi giá trị (x,y) của số bit trao đổi giữa Alice và Bob cộng với số bit thông tin nhận được từ máy tiên tri.

Một cách định nghĩa khác là thông qua việc đếm số hình chữ nhật tổ hợp toàn 1 ít nhất cần dùng để phủ tất cả các phần tử một trong ma trận 0/1 của hàm cần tính [2][3]. Độ phức tạp truyền thông không đơn định chính là lôgarit cơ số 2 của số hình chữ nhật tổ hợp toàn 1 ít nhất cần dùng để phủ tất cả các phần tử một trong ma trận.

Độ phức tạp truyền thông không đơn định là một cách để chặn dưới độ phức tạp truyền thông đơn định [3]. Đồng thời, trong lý thuyết ma trận không âm, nó cũng được dùng làm chặn dưới của hạng không âm của một ma trận không âm.[4]